#include <stdio.h>
#include <stdlib.h>

// 【反转链表】

// 定义元素类型（此处为int，可根据需求修改）
typedef int ElemType;

// 链表节点结构
typedef struct LNode
{
  ElemType data;      // 数据域：存储元素值
  struct LNode *next; // 指针域：指向下一个节点
} LNode, *LinkList;   // LNode为节点类型，LinkList为头指针类型

// ---------------------- 函数1：尾插法创建链表 ----------------------
void CreateListTail(LinkList *L, int n)
{
  // 1. 创建头节点
  *L = (LinkList)malloc(sizeof(LNode));
  if (*L == NULL)
  {
    printf("Memory allocation failed!\n");
    exit(1); // 内存分配失败，退出程序
  }
  (*L)->next = NULL; // 头节点初始无后继
  LNode *rear = *L;  // 尾指针，初始指向头节点

  // 2. 循环插入n个节点（尾插法）
  printf("Enter %d integers:\n", n);
  for (int i = 0; i < n; i++)
  {
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL)
    {
      printf("Memory allocation failed!\n");
      exit(1);
    }
    scanf("%d", &newNode->data); // 输入节点值
    newNode->next = NULL;        // 新节点初始无后继
    rear->next = newNode;        // 尾节点的next指向新节点
    rear = newNode;              // 尾指针后移至新节点
  }
}

// ---------------------- 函数2：打印链表 ----------------------
void PrintList(LinkList L)
{
  LNode *p = L->next; // 跳过头节点，从第一个元素节点开始遍历
  while (p != NULL)
  {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
}

// ---------------------- 函数3：反转链表（核心逻辑） ----------------------
void ReverseList(LinkList *L)
{
  // 空链表或只有头节点，无需反转
  if (*L == NULL || (*L)->next == NULL)
    return;

  LNode *prev = NULL;       // 前驱节点（初始为NULL，对应反转后末尾的NULL）
  LNode *curr = (*L)->next; // 当前要反转的节点（从第一个元素节点开始）
  LNode *next = NULL;       // 保存下一个节点的临时指针

  // 循环反转每个节点的指针
  while (curr != NULL)
  {
    next = curr->next; // 保存下一个节点，防止断链
    curr->next = prev; // 反转当前节点的next指针（指向前驱）
    prev = curr;       // 前驱指针后移
    curr = next;       // 当前指针后移
  }

  (*L)->next = prev; // 头节点的next指向反转后的第一个节点
}

// ---------------------- 主函数：测试逻辑 ----------------------
int main()
{
  LinkList L; // 链表头指针
  int n;      // 链表节点个数

  printf("Enter the number of nodes: ");
  scanf("%d", &n);

  // 1. 创建链表
  CreateListTail(&L, n);

  // 2. 打印原始链表
  printf("Original list: ");
  PrintList(L);

  // 3. 反转链表
  ReverseList(&L);

  // 4. 打印反转后的链表
  printf("Reversed list: ");
  PrintList(L);

  // 5. 释放链表内存（防止内存泄漏）
  LNode *p = L;
  LNode *temp;
  while (p != NULL)
  {
    temp = p;
    p = p->next;
    free(temp);
  }

  return 0;
}